#include <bits/stdc++.h>
using namespace std;

/*
3370. 仅含置位位的最小整数
已解答
简单
相关标签
premium lock icon
相关企业
提示
给你一个正整数 n。

返回 大于等于 n 且二进制表示仅包含 置位 位的 最小 整数 x 。

置位 位指的是二进制表示中值为 1 的位。

 

示例 1：

输入： n = 5

输出： 7

解释：

7 的二进制表示是 "111"。

示例 2：

输入： n = 10

输出： 15

解释：

15 的二进制表示是 "1111"。

示例 3：

输入： n = 3

输出： 3

解释：

3 的二进制表示是 "11"。

 

提示：

1 <= n <= 1000
*/

// 法一
class Solution {
public:
    int smallestNumber(int n) {
        // __builtin_clz返回前导零个数，32-其值为位数
        // n 的 二进制位数
        int k = 32 - __builtin_clz(n);
        int full = (1 << k) - 1;

        return full >= n ? full : (1 << (k + 1)) - 1;
    }
};

// 法二
class Solution {
public:
    int smallestNumber(int n) {
        // 即 2^k - 1  找到最小的 2^k - 1 且 >= n
        // n 的 二进制位数
        int cur = 1;
        while (cur < n) cur = cur * 2  + 1;
        return cur;
    }
};